/*
 * @lc app=leetcode.cn id=518 lang=golang
 *
 * [518] 零钱兑换 II
 */

// @lc code=start
func change(amount int, coins []int) int {
	// 完全背包问题
	m := len(coins)
	n := amount
	dp := make([][]int, m+1)
	for i, _ := range dp {
		dp[i] = make([]int, n+1)
	}
	dp[0][0] = 1
	// 对于完全背包问题，其中的内容可以无穷使用
	// 因此，我们每次选取了coins[i]后，我们依然可以使用这个 coins
	// 因此选取后的种类 = dp[i][j-coins[i]]
	// 但是在01背包问题中选取后的种类 = dp[i-1][j-coins[i]]
	// 注释：总方法数=选取后的方法数+未选取的方法
	for i := 1; i <= m; i++ {
		for j := 0; j <= n; j++ {
			if j < coins[i-1] {
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = dp[i][j-coins[i-1]] + dp[i-1][j]
			}
		}
	}
	return dp[m][n]
}
func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}

// @lc code=end

